import java.util.*;

class Solution {

    private final static int[][] DIR = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int H = heights.length, W = heights[0].length;
        boolean[][] pacific = new boolean[H][W];
        boolean[][] atlantic = new boolean[H][W];

        for (int r = 0; r < H; r++) {
            bfs(heights, r, 0, pacific);
            bfs(heights, r, W - 1, atlantic);
        }
        for (int c = 0; c < W; c++) {
            bfs(heights, 0, c, pacific);
            bfs(heights, H - 1, c, atlantic);
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int r = 0; r < H; r++) {
            for (int c = 0; c < W; c++) {
                if (pacific[r][c] && atlantic[r][c]) {
                    result.add(Arrays.asList(r, c));
                }
            }
        }
        return result;
    }

    private boolean inBounds(int[][] heights, int r, int c) {
        int H = heights.length, W = heights[0].length;
        return r >= 0 && r < H && c >= 0 && c < W;
    }

    private void dfs(int[][] heights, int r, int c, boolean[][] visited) {
        visited[r][c] = true;
        for (int[] dir : DIR) {
            int nextR = r + dir[0];
            int nextC = c + dir[1];
            if (inBounds(heights, nextR, nextC) && heights[nextR][nextC] >= heights[r][c] && !visited[nextR][nextC]) {
                dfs(heights, nextR, nextC, visited);
            }
        }
    }

    private void bfs(int[][] heights, int r, int c, boolean[][] visited) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{r, c});
        visited[r][c] = true;
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            r = pos[0];
            c = pos[1];
            for (int[] dir : DIR) {
                int nextR = r + dir[0];
                int nextC = c + dir[1];
                if (inBounds(heights, nextR, nextC)
                        && !visited[nextR][nextC]
                        && heights[nextR][nextC] >= heights[r][c]) {
                    queue.offer(new int[]{nextR, nextC});
                    visited[nextR][nextC] = true;
                }
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}